import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.Map;

public class LRUNodeCache {
    class Node{
       public Node pre;
       public Node next;
       public int key;
       public int value;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUNodeCache(int size) {
        this.size = size;
    }

    int size;
    Map<Integer,Node> map = new HashMap<>();
    public Node head=null;
    public Node tail =null;
    public void put(Integer key,Integer value){
        //key 是否存在
        if (map.containsKey(key)) {
            //存在，且是尾结点
            Node cur =map.get(key);
            if (cur==tail) {
                tail.value=value;
            }else if (cur==head){
                //头结点
                head.value=value;
                //尾结点与头节点建立双向指针
                tail.next=head;
                head.pre=tail;
                //指针后移
                tail=tail.next;
                head=head.next;
                //断开
                head.pre=null;
                tail.next=null;
            }else {
                cur.pre.next=cur.next;
                cur.next.pre=cur.pre;

                cur.next=null;
                cur.pre=null;

                //更新值
                Node tmp = new Node(key,value);
                tmp.pre=tail;
                tail.next=tmp;
                //尾指针后移
                tail=tail.next;
            }
        }else {
            Node node = new Node(key,value);
            if (map.isEmpty()){
                //空的，创建一个节点。
                head=tail=node;
            }else {
                //满了，删除一个最久未访问的数据
                if (map.size()==size){
                    map.remove(head.key);
                    Node tmp =head;
                    //头指针后移
                    head=head.next;
                    //断开双向指针
                    head.pre=null;
                    tmp.next=null;
                }
                //尾结点后增加一个节点，并建立双向指针
                tail.next=node;
                node.pre=tail;
                //尾结点后移
                tail=tail.next;
            }
            map.put(key,node);
        }
    }

    public int get(Integer key){
        if (map.containsKey(key)) {
            Integer value =map.get(key).value;
            put(key,value);
            return value;
        }else {
            return -1;
        }
    }

    public static void main(String[] args) {
        LRUNodeCache lruNodeCache = new LRUNodeCache(4);
        lruNodeCache.put(1,1);
        lruNodeCache.put(2,2);
        lruNodeCache.put(3,3);
        lruNodeCache.put(4,4);
        lruNodeCache.put(2,5);
        System.out.println(lruNodeCache.tail);
    }
}
